package com.zxy.leetcode._00000_00099._00040_00049;

import java.util.*;

/**
 * https://leetcode-cn.com/problems/permutations-ii/
 *
 * 全排列 II
 * 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
 *
 * 标签：回溯算法
 *
 */
public class Test00047 {

    public static void main(String[] args) {
        Test00047 test = new Test00047();

        int[] nums1 = {1, 1, 2};
        System.out.println(test.permuteUnique(nums1));

        int[] nums2 = {1, 2, 3};
        System.out.println(test.permuteUnique(nums2));
    }

    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();

        Map<Integer, Integer> countMap = new HashMap<>();
        Set<Integer> set = new LinkedHashSet<>();
        for (int num : nums) {
            set.add(num);

            countMap.compute(num, (k, v) -> {
                if (v == null) {
                    return 1;
                }else {
                    return ++v;
                }
            });
        }

        // allNums 是 nums 的去重及排序
        Integer[] allNums = new Integer[set.size()];
        set.toArray(allNums);

        backtrack(result, new ArrayDeque<>(), nums.length, countMap, allNums);

        return result;
    }

    private void backtrack(List<List<Integer>> result, Deque<Integer> selectNums, int len, Map<Integer, Integer> countMap, Integer[] nums) {
        if (selectNums.size() == len) {
            result.add(new ArrayList<>(selectNums));
            return;
        }

        for (int num : nums) {
            long count = selectNums.stream().filter(item -> item == num).count();
            if (countMap.getOrDefault(num, 0).intValue() == count) {
                continue;
            }

            selectNums.add(num);
            backtrack(result, selectNums, len, countMap, nums);
            selectNums.removeLast();
        }

    }

}
